package everydayGrade.t0;

/**
 * @Author: Siantar
 * @Date: 2023-12-14-15:19
 * @Description: 1.0
 */
public class T2132 {
    public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {
        int n = grid.length, m = grid[0].length;
        int[][] s = new int[n + 1][m + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + grid[i][j];
            }
        }
        int[][] d = new int[n + 2][m + 2];
        for (int i2 = stampHeight; i2 < n + 1; i2++) {
            for (int j2 = stampWidth; j2 < m + 1; j2++) {
                int i1 = i2 - stampHeight;
                int j1 = j2 - stampWidth;
                if (s[i2][j2] - s[i2][j1] - s[i1][j2] + s[i1][j1] == 0) {
                    d[i1 + 1][j1 + 1]++;
                    d[i1 + 1][j2 + 1]--;
                    d[i2 + 1][j1 + 1]--;
                    d[i2 + 1][j2 + 1]++;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                d[i + 1][j + 1] += d[i][j + 1] + d[i + 1][j] - d[i][j];
                if (grid[i][j] == 0 && d[i + 1][j + 1] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}
